package com.jia.leetCode;

/**
 * 123. 买卖股票的最佳时机 III
 */
public class Pro0123 {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int[][][] dp = new int[prices.length][2][3]; //2中，0表示没持有和1持有股票，3表示交易的笔数
        dp[0][1][0] = -prices[0];
        dp[0][1][1] = -prices[0];
        dp[0][1][2] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    if(k == 0 && j == 0) continue;
                    if(j == 1) {
                        dp[i][1][k] = Math.max(dp[i-1][0][k] - prices[i], dp[i-1][1][k]);
                    }else {
                        dp[i][0][k] = Math.max(dp[i-1][1][k-1] + prices[i], dp[i-1][0][k]);
                    }
                }
            }
        }
        int profit = Math.max(dp[prices.length - 1][0][2], dp[prices.length - 1][0][1]);
        return profit > 0? profit : 0;
    }

    public static void main(String[] args) {
        Pro0123 pro0123 = new Pro0123();
        System.out.println(pro0123.maxProfit(new int[]{1,2,3}));;
    }
}
